package lc301;//给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
//
// 返回所有可能的结果。答案可以按 任意顺序 返回。
//
//
//
// 示例 1：
//
//
//输入：s = "()())()"
//输出：["(())()","()()()"]
//
//
// 示例 2：
//
//
//输入：s = "(a)())()"
//输出：["(a())()","(a)()()"]
//
//
// 示例 3：
//
//
//输入：s = ")("
//输出：[""]
//
//
//
//
// 提示：
//
//
// 1 <= s.length <= 25
// s 由小写英文字母以及括号 '(' 和 ')' 组成
// s 中至多含 20 个括号
//
// Related Topics 广度优先搜索 字符串 回溯 👍 556 👎 0

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 301. 删除无效的括号
 * <a href="https://leetcode-cn.com/problems/remove-invalid-parentheses/"/>
 * 回溯算法
 * time:O(n*2的n次方)
 * space:O(n平方)
 * spend: >60m 研究回溯和符号匹配
 */
class Solution {

    List<String> res = new ArrayList<>();

    public List<String> removeInvalidParentheses(String s) {
        // 计算出要溢出的左右括号数
        int lrNum = 0;
        int rrNum = 0;
        for(int i = 0; i < s.length(); i++){
            char cur = s.charAt(i);
            if(cur == '('){
                lrNum++;
            }
            if(cur == ')'){
                if(lrNum == 0){
                    rrNum++;
                }else{
                    lrNum--;
                }
            }
        }
        backTrack(0, lrNum, rrNum, s);
        return res;
    }

    /** 回溯，移除括号 */
    void backTrack(int start, int lr, int rr, String s) {
        // 完成条件
        if(lr == 0 && rr == 0 && isValid(s)){
            res.add(s);
        }
        // for s （1.离开条件、2.做出选择、3.回溯、4.撤销选择）
        for(int i = start; i < s.length(); i++){
            // 1.离开条件
            if(i > start && s.charAt(i) == s.charAt(i - 1)){
                continue;
            }
            // 2.做出选择
            if(s.charAt(i) == '(' && lr > 0){
                //3.回溯 4.撤销选择
                backTrack(i, lr - 1, rr, s.substring(0, i) + s.substring(i + 1));
            }
            if(s.charAt(i) == ')' && rr > 0){
                //3.回溯 4.撤销选择
                backTrack(i, lr, rr - 1, s.substring(0, i) + s.substring(i + 1));
            }
        }
    }

    /** 判断是否有效 */
    boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        int length = s.length();
        int i = 0;
        while(i < length){
            if(s.charAt(i) != '(' && s.charAt(i) != ')'){
                i++;
                continue;
            }
            if(!stack.isEmpty() && s.charAt(i) == ')' && stack.peek() == '('){
                stack.pop();
                i++;
                continue;
            }
            stack.push(s.charAt(i));
            i++;
        }
        return stack.isEmpty();
    }

}
//leetcode submit region end(Prohibit modification and deletion)
